
#ifndef ___FANXES_DISJOINT_SET_H_
#define ___FANXES_DISJOINT_SET_H_

#include "AlogException.h"


template<class T>
class DisjointSet {
  public:
    DisjointSet( int n );
    ~DisjointSet();

    T Find( T e );

    DisjointSet<T>& Union( T i, T j )
    {
        parent[j] = i;

        return *this;
    }


  private:
    T *parent;
};



//----

template<class T>
DisjointSet<T>::DisjointSet( int n )
{
    parent = new T[n+1];

    for ( int e = 1; e <= n; e++ )
        parent[e] = 0;
}

template<class T>
DisjointSet<T>::~DisjointSet()
{
    delete [] parent;
}

template<class T>
T DisjointSet<T>::Find( T e )
{
    while ( parent[e] )
        e = parent[e];

    return e;
}

#endif // ___FANXES_DISJOINT_SET_H_

